package main.leetcode.clockin.March;

/**
 * 1013.将数组分成和相等的三个部分
 *
 * <p>给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
 *
 * <p>形式上，如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] +
 * A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。
 *
 * <p>
 *
 * <p>示例 1： 输出：[0,2,1,-6,6,-7,9,1,2,0,1] 输出：true 解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
 *
 * <p>示例 2： 输入：[0,2,1,-6,6,7,9,-1,2,0,1] 输出：false
 *
 * <p>示例 3： 输入：[3,3,6,5,-2,2,5,1,-9,4] 输出：true 解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
 *
 * <p>提示： 3 <= A.length <= 50000 -10^4 <= A[i] <= 10^4
 *
 * <p>来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day11 {
    public static void main(String[] args) {
        System.out.println(
                new day11().canThreePartsEqualSum(new int[] {0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1}));
    }

    //   public boolean canThreePartsEqualSum(int[] A) {
    //     int n = A.length;
    //     int l, r;
    //     int sum1 = 0, sum2 = 0, sum3 = 0;
    //     for (int i = 0; i < n - 2; i++) {
    //       sum1 += A[i];
    //       l = i + 1;
    //       r = n - 1;
    //       sum2 = A[l];
    //       sum3 = A[r];
    //       while (l < r) {
    //         if (sum1 == sum2 && sum1 == sum3 && l + 1 == r) return true;
    //         else if (sum1 == sum2) {
    //           sum3 += A[--r];
    //         } else if (sum1 == sum3) {
    //           sum2 += A[++l];
    //         } else {
    //           sum2 += A[++l];
    //           sum3 += A[--r];
    //         }
    //       }
    //     }
    //     return false;
    //   }

    // 寻找切点
    //  public boolean canThreePartsEqualSum(int[] A) {
    //    int n = A.length;
    //    int sum = 0, sum1 = A[0];
    //    for (int val : A) sum += val; // 求总和
    //    if (sum % 3 != 0) return false; // 总和不是3的倍数直接返回false
    //    sum /= 3;
    //    int i;
    //    for (i = 1; i < n - 2 && sum1 != sum; i++) sum1 += A[i]; // 找到第一个切点（贪心）
    //    sum1 = 0;
    //    while (i < n - 1) { // 寻找j点，满足A[i]+A[i+1]+...+A[j-1] = sum/3
    //      sum1 += A[i];
    //      if (sum == sum1) return true;
    //      i++;
    //    }
    //    return false;
    //  }

    // 双指针
    public boolean canThreePartsEqualSum(int[] A) {
        int n = A.length;
        int sum = 0;
        for (int val : A) sum += val; // 求总和
        if (sum % 3 != 0) return false; // 总和不是3的倍数直接返回false
        sum /= 3;
        int l = 0, r = n - 1;
        int sum1 = A[l], sum2 = A[r];
        while (l < r - 1) { // 中间部分不为空
            if (sum == sum1 && sum == sum2) return true;
            else if (sum == sum1) sum2 += A[--r];
            else if (sum == sum2) sum1 += A[++l];
            else {
                sum1 += A[++l];
                sum2 += A[--r];
            }
        }
        return false;
    }
}
